package array;

import java.util.Arrays;

public class Ex152 {
    static class Solution {

        //能让题目解出的方法只有一个，那就是维护两个数组
        //在维护最大值的同时，也要维护一个最小值数组
        //这样，在遇到负数的时候，立马从最小值中取得，与负数相乘得最大值
        public int maxProduct1(int[] nums) {
            int m;
            if (nums == null || (m = nums.length) == 0) return 0; 
            int max[] = new int[m];
            int min[] = new int[m];

            //表示以i为最后值的最大值
            max[0] = nums[0];
            min[0] = nums[0];
            int res = max[0];
            for (int i = 1; i < m; i++) {
                if (nums[i] < 0) {
                    max[i] = Math.max(min[i - 1] * nums[i], nums[i]);
                    min[i] = Math.min(max[i - 1] * nums[i], nums[i]);
                } else if (nums[i] > 0) {
                    max[i] = Math.max(nums[i] * max[i - 1], nums[i]);
                    min[i] = Math.min(nums[i], nums[i] * min[i - 1]);
                } else max[i] = 0;
                res = Math.max(res, max[i]);
            }
            System.out.println(Arrays.toString(max) + "      " + Arrays.toString(min));
            return res;
        }

        //优化空间
        public int maxProduct2(int[] nums) {
            int m;
            if (nums == null || (m = nums.length) == 0) return 0; 
            int max = nums[0], min = nums[0];
            int res = max;
            for (int i = 1; i < m; i++) {
                System.out.println(max + "      " + min);
                if (nums[i] < 0) {
                    int temp = max;
                    max = Math.max(min * nums[i], nums[i]);
                    min = Math.min(temp * nums[i], nums[i]);
                } else if (nums[i] > 0) {
                    // int temp = max;
                    max = Math.max(nums[i] * max, nums[i]);
                    min = Math.min(nums[i], nums[i] * min);
                } else {
                    max = 0;
                    min = 0;
                }
                res = Math.max(res, max);
            }
            System.out.println(max + "      " + min);
            return res;
        }

        //最弔方法：数学规律

        //若负数值为偶数个，则最大值必为所有数相乘
        //若有奇数个负数，除了边界那个负数之外另一边的值。

        //难点在于遇到0的情况：当遇到0时，不把结果变成0，而是重置为1
        public int maxProduct(int[] nums) {
            int m;
            if (nums == null || (m = nums.length) == 0) return 0; 
            int l = 0, r = 0, max = nums[0];
            for (int i = 0; i < m; i++) {
                l = (l == 0) ? 1 : l * nums[i];
                r = (r == 0) ? 1 : r * nums[m - i - 1];
                max = Math.max(max, Math.max(l, r));
            }
            return max;
        }



        public static void main(String[] args) {
            int[] nums = new int[] {-2, 0 , -1};
            int res = new Solution().maxProduct(nums);
            System.out.println(res);
        }


        int p[][];
        int[] nums;
        public int maxProductX(int[] nums) {
            int m;
            if (nums == null || (m = nums.length) == 0) return 0; 
            p = new int[m][m];
            this.nums = nums;
            Arrays.fill(p, Integer.MAX_VALUE);
            for (int i = 0; i < m; i++) {
                //乘积至少含有一个
                p[i][i] = nums[i];
            }
            return dfs (0, 1);
        }

        public int dfs(int i, int cur) {
            if (i == p.length) {
                return cur;
            }
            int self = cur * nums[i];
            int post = dfs(i + 1, self);
            return Math.max(self, post);
        }

       
    }
}
